|
|
Automata in Infinite-state Formal Verification
Lengál, Ondřej ; Jančar, Petr (oponent) ; Veith, Helmut (oponent) ; Esparza, Javier (oponent) ; Vojnar, Tomáš (vedoucí práce)
The work presented in this thesis focuses on finite state automata over finite words and finite trees, and the use of such automata in formal verification of infinite-state systems. First, we focus on extensions of a previously introduced framework for verifi cation of heap-manipulating programs-in particular programs with complex dynamic data structures-based on tree automata. We propose several extensions to the framework, such as making it fully automated or extending it to consider ordering over data values. Further, we also propose novel decision procedures for two logics that are often used in formal verification: separation logic and weak monadic second order logic of one successor. These decision procedures are based on a translation of the problem into the domain of automata and subsequent manipulation in the target domain. Finally, we have also developed new approaches for efficient manipulation with tree automata, mainly for testing language inclusion and for handling automata with large alphabets, and implemented them in a library for general use. The developed algorithms are used as the key technology to make the above mentioned techniques feasible in practice.
|
|
|
Harnessing Forest Automata for Verification of Heap Manipulating Programs
Šimáček, Jiří ; Abdulla, Parosh (oponent) ; Křetínský, Mojmír (oponent) ; Vojnar, Tomáš (vedoucí práce)
This work addresses verification of infinite-state systems, more specifically, verification of programs manipulating complex dynamic linked data structures. Many different approaches emerged to date, but none of them provides a~sufficiently robust solution which would succeed in all possible scenarios appearing in practice. Therefore, in this work, we propose a new approach which aims at improving the current state of the art in several dimensions. Our approach is based on using tree automata, but it is also partially inspired by some ideas taken from the methods based on separation logic. Apart from that, we also present multiple advancements within the implementation of various tree automata operations, crucial for our verification method to succeed in practice. Namely, we provide an optimised algorithm for computing simulations over labelled transition systems which then translates into more efficient computation of simulations over tree automata. We also give a new algorithm for checking inclusion over tree automata, and we provide experimental evaluation demonstrating
|
|
| |
|
|
Těžba uranu, její dopad na životní prostředí a rekultivace
Peterková, Alena ; Malíček, Jiří (vedoucí práce) ; Frouz, Jan (oponent)
Česká republika v minulosti patřila mezi významná území z hlediska těžby nerostných surovin. V období po druhé světové válce se stala velmi významným dobyvatelem uranové rudy, na kterou mnohonásobně vzrostla celosvětová poptávka díky rozvoji jaderné energetiky a masivní produkci nukleárních zbraní. V období osmdesátých let minulého století však zájem o uran poklesl a v devadesátých letech 20. století byly již téměř všechny uranové doly na našem území uzavřeny. Posledním místem těžby uranu byl důl Rožná, ve kterém bylo těženo až do roku 2017. V současné době probíhají na lokalitách rekultivační práce. Naplánování rekultivace pro dané území není však vždy jednoduchou záležitostí. Musí být brán v potaz způsob těžby, který byl na daném území prováděn, podloží, vzdálenost obydlí, podzemní vody, fauna a flóra okolí apod. Často jsou rekultivace prováděny nesprávným způsobem, a tím není dostatečně využit výjimečný potenciál biotopů zde vzniklých. Lidé mají tendence do obnovy krajiny silně zasahovat, jak už dodáváním živin, tak i vysazováním rostlinných druhů, a tím vytvářet intenzivní hospodářskou krajinu. Často si ovšem neuvědomují, že těžbou byla na lokalitě způsobena výrazná změna abiotických podmínek. Nově vzniklá stanoviště byla v mnohých případech osídlena vzácnými a ohroženými organismy, které jsou...
|
|
|
Těžba uranu, její dopad na životní prostředí a rekultivace
Peterková, Alena ; Malíček, Jiří (vedoucí práce) ; Frouz, Jan (oponent)
Česká republika v minulosti patřila mezi významná území z hlediska těžby nerostných surovin. V období po druhé světové válce se stala velmi významným dobyvatelem uranové rudy, na kterou mnohonásobně vzrostla celosvětová poptávka díky rozvoji jaderné energetiky a masivní produkci nukleárních zbraní. V období osmdesátých let minulého století však zájem o uran poklesl a v devadesátých letech 20. století byly již téměř všechny uranové doly na našem území uzavřeny. Posledním místem těžby uranu byl důl Rožná, ve kterém bylo těženo až do roku 2017. V současné době probíhají na lokalitách rekultivační práce. Naplánování rekultivace pro dané území není však vždy jednoduchou záležitostí. Musí být brán v potaz způsob těžby, který byl na daném území prováděn, podloží, vzdálenost obydlí, podzemní vody, fauna a flóra okolí apod. Často jsou rekultivace prováděny nesprávným způsobem, a tím není dostatečně využit výjimečný potenciál biotopů zde vzniklých. Lidé mají tendence do obnovy krajiny silně zasahovat, jak už dodáváním živin, tak i vysazováním rostlinných druhů, a tím vytvářet intenzivní hospodářskou krajinu. Často si ovšem neuvědomují, že těžbou byla na lokalitě způsobena výrazná změna abiotických podmínek. Nově vzniklá stanoviště byla v mnohých případech osídlena vzácnými a ohroženými organismy, které jsou...
|
|
|
Automata in Infinite-state Formal Verification
Lengál, Ondřej ; Jančar, Petr (oponent) ; Veith, Helmut (oponent) ; Esparza, Javier (oponent) ; Vojnar, Tomáš (vedoucí práce)
The work presented in this thesis focuses on finite state automata over finite words and finite trees, and the use of such automata in formal verification of infinite-state systems. First, we focus on extensions of a previously introduced framework for verifi cation of heap-manipulating programs-in particular programs with complex dynamic data structures-based on tree automata. We propose several extensions to the framework, such as making it fully automated or extending it to consider ordering over data values. Further, we also propose novel decision procedures for two logics that are often used in formal verification: separation logic and weak monadic second order logic of one successor. These decision procedures are based on a translation of the problem into the domain of automata and subsequent manipulation in the target domain. Finally, we have also developed new approaches for efficient manipulation with tree automata, mainly for testing language inclusion and for handling automata with large alphabets, and implemented them in a library for general use. The developed algorithms are used as the key technology to make the above mentioned techniques feasible in practice.
|
|
|
Harnessing Forest Automata for Verification of Heap Manipulating Programs
Šimáček, Jiří ; Abdulla, Parosh (oponent) ; Křetínský, Mojmír (oponent) ; Vojnar, Tomáš (vedoucí práce)
This work addresses verification of infinite-state systems, more specifically, verification of programs manipulating complex dynamic linked data structures. Many different approaches emerged to date, but none of them provides a~sufficiently robust solution which would succeed in all possible scenarios appearing in practice. Therefore, in this work, we propose a new approach which aims at improving the current state of the art in several dimensions. Our approach is based on using tree automata, but it is also partially inspired by some ideas taken from the methods based on separation logic. Apart from that, we also present multiple advancements within the implementation of various tree automata operations, crucial for our verification method to succeed in practice. Namely, we provide an optimised algorithm for computing simulations over labelled transition systems which then translates into more efficient computation of simulations over tree automata. We also give a new algorithm for checking inclusion over tree automata, and we provide experimental evaluation demonstrating
|
|
| |
|
|
Vyhodnocení úspěšnosti lesnické rekultivace po těžbě černého uhlí v okolí Orlové
Cagašová, Kateřina
Cílem bakalářské práce bylo vyhodnocení úspěšnosti lesnické rekultivace na vybraných územích v okolí města Orlové a navrhnout případná opatření, díky kterým by mohl být zlepšen přístup vzhledem k realizacím technických a následně i biologických rekultivací v rámci sanace území poznamenaných hlubinnou těžbou uhlí. Vyhodnocení úspěšnosti rekultivace probíhalo s důrazem na vyhodnocení přípravy stanoviště před výsadbou, použité dřeviny, péči o kultury a porosty, ztráty, délku nadzemní části, tloušťku kmene, tvar kmene a koruny, vitalitu a poškození. Následná opatření byla navrhována s ohledem na charakter stanoviště a podmínky, které podmiňují vlastní perspektivní růst dřeviny. Práce čerpala z dostupných materiálů a dokumentací, které vznikaly od počátku plánování samotných rekultivací. Další údaje byly doplněny měřením potřebných dendrometrických veličin na samotných dřevinách a analýzou stanoviště. Na základě vyhodnocení jednotlivých průzkumů stanovišť byl popsán současný stav porostů, zhodnocena jejich kvalita a navržena opatření pro následnou péči. V rámci této práce bylo rovněž poukázáno na nevhodné kroky včetně zastoupení ne vždy vhodných druhů dřevin ve vztahu k poskytovaným podmínkám růstu na stanovišti tvořeném z různě mocných návozů hlušiny a ornice u některých rekultivačních akcí. Závěrem bylo zhodnocení realizovaných technických zásahů ve vztahu k druhové skladbě dřevin a jejich následné výsadbě, včetně návrhu směřujících ke zkvalitnění výsadeb a dosažení kvalitního cílového porostu.
|
|
|
Vliv okolní vegetace na průběh sukcese na kladenských haldách
DVOŘÁKOVÁ, Helena
Předmětem této práce bylo zhodnotit vliv okolní vegetace na druhové složení kladenských hald po těžbě černého uhlí. V průběhu vegetačních sezón 2009-2011 byla zaznamenána abundance druhů na haldách a jejich okolí do 100 m a následně zpracována za použití ordinačních metod (DCA a CCA) a jednorozměrných statistických metod. Zdá se, že na druhové složné vegetace hald mají vliv typy land cover a procento starého lesa přítomné v letech 1836 - 1852 do 100 m a 1 km od okraje haldy.
|
host ::
RSS.